

# +    -     *【乘法】 /【除法】 %【求余或者取模】 **【求幂或者几次方】 //【取整】

# 基数排序
# （1）通过键值得各个位的值，将要排序的元素分配至一些桶中，达到排序的作用
# [] {}
# （2）基数排序法是属于稳定性的排序，基数排序法是效率高的稳定排序法
# []
# （3）基数排序是桶排序的扩展

# 实现步骤
# （1）确定数组中的最大元素有几位（MAX）（确定执行的轮数）# 125 , 78
#                                                           3      2

# （2）创建0~9个桶（桶的底层是队列），因为所有的数字元素都是由0~9的十个数字组成
# {0--9}
# （3）依次判断每个元素的个位，十位至MAX位，存入对应的桶中，出队，存入原数组；直至MAX轮结束输出数组。
#
# （4）具体实现步骤


blist = [50, 44, 2, 3, 26, 56, 47, 15, 5, 38, 37, 125, 78, 65, 45, 25, 52, 12, 2, 7, 75, 72]


def RadixSort(alist):
    number = 0 # number个数
    n = 1 # n最大字符的个数
    max_num = max(alist) # 求出列表中的最大数
    # 循环最大数， 当最大数大于个数（n）乘以10的时候则个数（n+1）
    while max_num > 10**n:
        n += 1
        # print(max_num)
        # print(n)
    # 2、构造桶
    # 桶可以是两种， 一种是字典， 一种是列表
    # 字典 barrel桶
    while number < n:
        barrel = {} # 构造一个字典
        for i in range(10):
            barrel.setdefault(i, []) # 将桶的值设为空值
            # print(barrel)
        for x in alist: # 对每一个桶的值进行排序
            barrel_value = int((x / (10**number)) % 10) # 得到每一位的基数 2 / 10 *10 % 10 0.2 2
            # print(barrel_value)
            barrel[barrel_value].append(x) # 将对应的数据加入到对应的桶中
            # print(barrel)
        j = 0
        for v in range(10):
            if len(barrel[v]) != 0 : # 判断桶里面的值是否为空
                # 不为空
                for t in barrel[v]: # 循环出桶中的每个元素
                    alist[j] = t # 返回给数组
                    j += 1
        # print(number)
        number += 1 # 个数+1
    print(alist)

RadixSort(blist) # 调用函数对象



